Proposal: Ordered Collection Diffing #21845

numist · 2019-01-14T19:15:06Z

This PR is an initial implementation of the Ordered Collection Diffing proposal, which was pitched on the forums in December.

… tests

Azoy · 2019-01-14T21:36:44Z

Nit: stdlib uses 2 space tabs

…tance

stdlib/public/core/CollectionDifference.swift

…edChanges:)

…k, causing some strange crashes

DevAndArtist

@numist several lines of this patch are too long. Stdlib uses 2 spaces tabs and has a maximum line width set to 80 characters.

stdlib/public/core/CollectionDifference.swift

lorentey

I had suggested a number of small(ish) adjustments -- mostly to follow the stdlib coding guidelines:

The fully qualified names of internal/private types (and members) must have at least one underscore-prefixed component. For initializers, we put the underscore in the label of the first parameter.
All declarations must have an explicit access level in the stdlib. (This is often redundant, but it helps a lot with reviewing what gets into the public API/ABI.)
When possible, we prefer to have meaningful names for generic type parameters, function parameters and local variables. (I think x, y etc. works fine in the core diffing implementation, though.)

stdlib/public/core/CollectionDifference.swift

stdlib/public/core/Diffing.swift

- Add an underscore to private/internal symbols - Make access levels explicit, even when they’re implied from context - Conform to max line length of 80 characters - Conformances declared on separate extensions that implement them - Arrange member declarations so that stored properties appear first - Expand single-letter function and type parameter names where there is an obvious name that’s more descriptive - RangeReplaceableCollection.fastApplicationEnumeration → CollectionDifference._fastEnumeratedApply

@DevAndArtist

Suggested by @DevAndArtist Co-Authored-By: numist <github@numist.net>

Preparations for landing numist/swift

DevAndArtist · 2019-02-27T13:26:58Z

I hope it won't get shipped with @available(macOS 9999, iOS 9999, tvOS 9999, watchOS 9999, *) by accident. 😅

moiseev · 2019-02-27T18:01:43Z

stdlib/public/core/CollectionDifference.swift

+  public init?<Changes: Collection>(
+    _ changes: Changes
+  ) where Changes.Element == Change {
+    if !CollectionDifference<ChangeElement>._validateChanges(changes) {


FWIW: there's an idiomatic way to spell if ! called guard. Some people prefer it for preconditions.

Oops, this actually used to be a guard but the code got refactored a number of times >_<

moiseev · 2019-02-27T18:11:15Z

stdlib/public/core/CollectionDifference.swift

+}
+
+@available(macOS 9999, iOS 9999, tvOS 9999, watchOS 9999, *) // FIXME(availability-5.1)
+extension CollectionDifference.Index { // Comparable


Can't the conformance be removed from the declaration above, and uncommented here?

moiseev · 2019-02-27T18:16:45Z

stdlib/public/core/Diffing.swift

+
+@available(macOS 9999, iOS 9999, tvOS 9999, watchOS 9999, *) // FIXME(availability-5.1)
+extension CollectionDifference {
+  fileprivate func _fastEnumeratedApply(


At some point only internal and public declarations were allowed in the stdlib. I wonder what happened to that rule. @lorentey, @milseman do you know?

I believe that private and fileprivate can work (but not as usableFromInline) in a world where we're not sil-serialize-all

We started to occasionally use private in the stdlib last year. It's still a bit unusual, and the fileprivate/private mess has annoying interactions with our rule for explicit access levels. But as far as I know, the technical issues we had before have all been resolved now.

moiseev · 2019-02-27T18:19:01Z

stdlib/public/core/Diffing.swift

+    func append(
+      into target: inout Self,
+      contentsOf source: Self,
+      from index: inout Self.Index, count: Int) {


The convention is to put a closing paren and the opening curly on the new line unindented after the parameter list.

moiseev · 2019-02-27T18:24:13Z

stdlib/public/core/Diffing.swift

+        enumeratedOriginals += origCount
+        enumeratedInserts += 1
+      }
+      assert(enumeratedOriginals <= self.count)


assert is rarely the right choice for the stdlib code. Consider using _precondition, _debugPrecondition, or _internalInvariant as described here.

moiseev · 2019-02-27T18:29:12Z

stdlib/public/core/Diffing.swift

+  }
+
+  fileprivate subscript(position: Index) -> Element {
+    precondition((startIndex..<endIndex).contains(position))


s/precondition/_precondition perhaps?

I think _internalInvariant is actually more appropriate here since this only provides early detection of a code defect that would fail further along regardless. I'll go through all the calls to assert and update as appropriate.

moiseev · 2019-02-27T18:34:14Z

stdlib/public/core/Diffing.swift

+    var (x, y) = (x, y)
+    let (n, m) = (a.endIndex, b.endIndex)
+
+    var v = _SearchState<Source.Index, Target.Index>(consuming: &pathStorage)


Vrbl nms R nt vry rdbl.

Sorry, too used to writing pure C—vowels are expensive!

For what it's worth, in this specific case the variable names are cribbed directly from the pseudocode in the Myers' paper (linked in the comments of this file) so they are canonical.

I think the terse names are justified here since the implementation follows the paper, and using the same notation makes the code easier to follow.

moiseev · 2019-02-27T18:40:47Z

test/stdlib/Diffing.swift

+
+  for (source, target, expected, line) in expectedChanges {
+    let actual = target.difference(from: source).inferringMoves()
+    expectEqual(actual, CollectionDifference(expected), "failed test at line \(line)")


StdlibUnittest expect functions take expected first and actual second.

moiseev · 2019-02-27T18:47:44Z

test/stdlib/Diffing.swift

+  let mine = "Is\nit\nreview\ntime\nalready?"
+
+  // Split the contents of the sources into lines
+  let baseLines = base.components(separatedBy: "\n")


Isn't it an NSString API? How is it even available here without import Foundation, I wonder.

Maybe through StdlibUnittest

I've only run the tests on Darwin, it seems likely that Foundation is getting imported somewhere. I'll make the test more literal.

moiseev · 2019-02-27T18:49:42Z

test/stdlib/Diffing.swift

+  let expectedChanges: [(
+    source: [String],
+    target: [String],
+    changes: [CollectionDifference<String>.Change],


Oh.. So we don't need availability checks if the APIs are marked as 9999?

Ah, good catch -- I haven't run the tests after the availability commit.

I still have to guard for it, but it will succeed at runtime

[test] Add missing runtime availability check around diffing tests

lorentey · 2019-03-01T01:02:22Z

@swift-ci please test

swift-ci · 2019-03-01T03:53:37Z

Build failed
Swift Test OS X Platform
Git Sha - ed7cabb

numist · 2019-03-05T05:30:28Z

@swift-ci please test

swift-ci · 2019-03-05T05:30:58Z

Build failed
Swift Test OS X Platform
Git Sha - 4f783fb

swift-ci · 2019-03-05T05:32:28Z

Build failed
Swift Test Linux Platform
Git Sha - 4f783fb

Catfish-Man · 2019-03-05T23:51:56Z

@swift-ci please test

swift-ci · 2019-03-06T01:10:50Z

Build failed
Swift Test Linux Platform
Git Sha - fcf6550

swift-ci · 2019-03-06T03:00:21Z

Build failed
Swift Test OS X Platform
Git Sha - fcf6550

lorentey · 2019-03-06T04:03:55Z

The macOS failure in Swift Syntax was fixed in apple/swift-syntax#106.
Foundation's test_xpath failure on Linux also seems unrelated; it hasn't occurred in neighboring builds.

19:10:48 Test Case 'TestXMLDocument.test_xpath' started at 2019-03-06 01:10:47.995
19:10:48 
19:10:48 
19:10:48 0% tests passed, 1 tests failed out of 1
19:10:48 
19:10:48 Total Test time (real) =  21.82 sec
19:10:48 
19:10:48 The following tests FAILED:
19:10:48 	  1 - TestFoundation (SEGFAULT)
19:10:48 Errors while running CTest
19:10:48 FAILED: CMakeFiles/test.util

lorentey · 2019-03-06T04:04:12Z

Third time the charm!

@swift-ci test

numist · 2019-03-06T07:09:07Z

@lorentey how did u do that

numist added 2 commits January 13, 2019 20:17

Initial import of diffing package into standard library

1af14db

Adapt the last of the Darwin- and XCTest-specific code in the diffing…

7c13fe3

… tests

numist requested review from dabrahams, lorentey, DougGregor and airspeedswift January 14, 2019 19:15

numist mentioned this pull request Jan 14, 2019

[Proposal] Ordered collection diffing apple/swift-evolution#968

Merged

numist added 4 commits January 14, 2019 15:53

Match indentation style

c0c068d

s/shortestEditScript/difference/g per proposal feedback

df3a058

Apply public documentation and type modifications from proposal accep…

b467e24

…tance

Include renamed CollectionDifference.swift

b7f36c3

dabrahams reviewed Feb 5, 2019

View reviewed changes

stdlib/public/core/CollectionDifference.swift Outdated Show resolved Hide resolved

numist added 2 commits February 5, 2019 14:34

Header docs for internal methods validateChanges(_:) and init(validat…

4552291

…edChanges:)

Only instanciate one test suite--this was confusing the test framewor…

9b45fc4

…k, causing some strange crashes

DevAndArtist suggested changes Feb 18, 2019

View reviewed changes

lorentey requested changes Feb 18, 2019

View reviewed changes

lorentey and others added 3 commits February 22, 2019 14:27

[stdlib] Set availability of diffing APIs

fd32a3d

Wrap < to fit in 80

5ed93b5

Suggested by @DevAndArtist Co-Authored-By: numist <github@numist.net>

numist changed the base branch from master to swift-5.1-branch February 26, 2019 23:51

numist added 2 commits February 26, 2019 15:53

Merge branch 'numist/diffing' into numist/diffing

23afad1

Merge pull request #1 from lorentey/numist/diffing

ed7cabb

Preparations for landing numist/swift

lorentey approved these changes Feb 27, 2019

View reviewed changes

moiseev reviewed Feb 27, 2019

View reviewed changes

numist and others added 3 commits February 27, 2019 14:05

Incorporate feedback from @lorentey and @moiseev

6e3139b

[test] Add missing runtime availability check around diffing tests

f414c16

Merge pull request #2 from lorentey/numist/diffing

4f783fb

[test] Add missing runtime availability check around diffing tests

numist changed the base branch from swift-5.1-branch to master March 5, 2019 05:19

Merge branch 'master' into numist/diffing

fcf6550

Catfish-Man merged commit 909868f into apple:master Mar 6, 2019

lorentey mentioned this pull request Mar 9, 2019

[5.1][SE-0240] Ordered Collection Diffing #23197

Merged

zntfdr mentioned this pull request Jul 25, 2019

[139] Issue #139 - July 25, 2019 SwiftWeekly/swiftweekly.github.io#468

Closed

Proposal: Ordered Collection Diffing #21845

Proposal: Ordered Collection Diffing #21845

Conversation

numist commented Jan 14, 2019

Azoy commented Jan 14, 2019

DevAndArtist left a comment

Choose a reason for hiding this comment

lorentey left a comment

Choose a reason for hiding this comment

DevAndArtist commented Feb 27, 2019

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

numist Feb 27, 2019 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

lorentey commented Mar 1, 2019

swift-ci commented Mar 1, 2019

numist commented Mar 5, 2019

swift-ci commented Mar 5, 2019

swift-ci commented Mar 5, 2019

Catfish-Man commented Mar 5, 2019

swift-ci commented Mar 6, 2019

swift-ci commented Mar 6, 2019

lorentey commented Mar 6, 2019

lorentey commented Mar 6, 2019

numist commented Mar 6, 2019

numist Feb 27, 2019 •

edited